package com.hy.Three394;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2024/4/21
 * Time:13:56
 */
public class MinimumOperations {

    /**
     *
     * @param grid 二维数组表示的网格，其中每个元素都是一个非负整数。
     * @return 返回使所有元素变为0所需的最小操作次数。
     */
    public int minimumOperations(int[][] grid) {
        int m = grid.length; // 网格的行数
        int n = grid[0].length; // 网格的列数
        int[][] cnt = new int[n][10]; // 用于存储每列每个数字的出现次数

        // 统计每列每个数字的出现次数
        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                cnt[j][row[j]]++;
            }
        }

        int[][] memo = new int[n][11]; // 用于存储子问题的解，避免重复计算
        for (int[] row : memo) {
            Arrays.fill(row, -1); // 初始化memo数组，-1表示没有计算过
        }

        // 递归求解并返回最小操作数
        return m * n - dfs(n - 1, 10, cnt, memo);
    }

    /**
     * 使用深度优先搜索（DFS）计算最优解。
     * @param i 当前位置的行索引
     * @param j 当前位置的列索引
     * @param cnt 存储每个位置可能的计数的二维数组
     * @param memo 用于记忆化搜索的二维数组，避免重复计算
     * @return 在当前位置选择最优解得到的总和
     */
    private int dfs(int i, int j, int[][] cnt, int[][] memo) {
        if (i < 0) { // 当前位置超出边界，返回0
            return 0;
        }
        if (memo[i][j] != -1) { // 如果之前计算过该位置的结果，直接返回记忆化结果
            return memo[i][j];
        }
        int res = 0; // 初始化结果为0
        for (int k = 0; k < 10; ++k) { // 遍历所有可能的下一个位置
            if (k != j) { // 当前位置不选择自己
                res = Math.max(res, dfs(i - 1, k, cnt, memo) + cnt[i][k]); // 递归计算并更新结果
            }
        }
        return memo[i][j] = res; // 将结果记忆化，并返回
    }
}
